package bitInterview;

import java.util.*;

/**
 * @author ZJX
 * @version 1.0
 * @descption
 * @since 2025/11/17 14:51
 */
public class Day37 {
    public String longestWord(String[] words) {
        Set<String> wordSet = new HashSet<>();
        for (String word : words) {
            wordSet.add(word);
        }
        Arrays.sort(words, (a, b) -> {
            if (a.length() != b.length()) {
                return b.length() - a.length();
            } else {
                return a.compareTo(b);
            }
        });
        for (String word : words) {
            boolean valid = true;
            for (int i = 1; i < word.length(); i++) {
                String prefix = word.substring(0, i);
                if (!wordSet.contains(prefix)) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                return word;
            }
        }
        return "";
    }

    public boolean canPartition(int[] nums) {
        int max = 0;
        int sum = 0;
        for (int n : nums) {
            sum += n;
            if (n > max) {
                max = n;
            }
        }
        if (sum % 2 == 1) {
            return false;
        }
        int target = sum / 2;
        if (max > target) {
            return false;
        }
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int n : nums) {
            for (int i = target; i >= n; i--) {
                dp[i] = dp[i] || dp[i - n];
            }
        }
        return dp[target];
    }

    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int left = 0;
        int ret = 0;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (map.containsKey(ch)) {
                left = Math.max(left, map.get(ch) + 1);
            }
            map.put(ch, i);
            ret = Math.max(ret, i - left + 1);
        }
        return ret;
    }

    public int myAtoi(String s) {
        int n = s.length();
        int i = 0;
        // 跳过空格
        while (i < n && s.charAt(i) == ' ') {
            i++;
        }
        int sign = 1;
        if (i < n && s.charAt(i) == '+') {
            i++;
        } else if (i < n && s.charAt(i) == '-') {
            sign = -1;
            i++;
        }
        int ret = 0;
        while (i < n && Character.isDigit(s.charAt(i))) {
            int digit = s.charAt(i) - '0';
            if (ret > (Integer.MAX_VALUE - digit) / 10) {
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            } else {
                ret = ret * 10 + digit;
            }
            i++;
        }
        return ret * sign;
    }

    public int longestValidParentheses(String s) {
        int n = s.length();
        int maxLen = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    maxLen = Math.max(maxLen, i - stack.peek());
                }
            }
        }
        return maxLen;
    }
}

